#include<stdio.h>
/*******************************常量部分****************************************/
#define OK 1
#define ERROR -1
#define INFINITY 999    //最大值
#define MAX_NUM 20 //最大顶点个数


/*******************************结构体定义部分****************************************/
typedef struct
{
    int adjvex;   //顶点
    int lowcost;  //最小值
} Closedge;

typedef struct
{
    int vexs[MAX_NUM]; //顶点向量
    int arcs[MAX_NUM][MAX_NUM];              //邻接矩阵
    int vexnum, arcnum;              //图的当前顶点数和弧数
} MGraph;

/*******************************函数定义部分****************************************/
int LocateVex(MGraph G, int op);
int CreateUDN(MGraph &G);
int Minimum(Closedge closedge[], int n);
void MiniSpanTree_PRIM(MGraph &G, int u);


int main()
{
    int op = 1;
    MGraph G;
    printf("******************************************************************************\n");
    printf("\t\t\t\t基于Prim算法的最小生成树\n");
    printf("\t0.Exit\n");
    printf("\t1.Continue\n");
    printf("******************************************************************************\n");


    while (op){
        printf("\n请选择你的操作[0-1]: ");
        scanf("%d",&op);
        switch (op) {
            case 1:
                if (CreateUDN(G)>=1) {
                    printf("\n输出生成树上的5条边为：\n");
                    MiniSpanTree_PRIM(G, 1);
                }
            case 0:
                break;
        }
    }
    printf("欢迎下次使用本系统!\n\n");

    return 0;
}




// 顶点地址校验
// 在邻接矩阵中是从 0~ n-1 开始与我们输入的顶点和弧数
int LocateVex(MGraph G, int op)
{
    int i;
    for (i = 0; i < G.vexnum; i++)
        if (G.vexs[i] == op)
            return i;
    return ERROR;
}


int CreateUDN(MGraph &G) {
    int i, j,w,v1,v2;       //i,j,k用于计数，w表示权重，v1v2表示弧头、弧尾
    printf("\n请输入顶点个数与弧个数：");
    scanf("%d %d",&G.vexnum,&G.arcnum);

    if (G.arcnum < G.vexnum-1 || G.arcnum > (G.vexnum * (G.vexnum - 1)) / 2)// 健全性判断
    {
        printf("输入边数不合法！，边数范围为[%d,%d]",G.vexnum-1,(G.vexnum * (G.vexnum - 1)) / 2);
        return ERROR;
    }


    for ( i = 0; i < G.vexnum; ++i) {
        G.vexs[i] = (i+1);
    }

    // 初始化
    for ( i = 0; i < G.vexnum; ++i) {
        for ( j = 0; j < G.vexnum; ++j) {
            G.arcs[i][j] = INFINITY;
        }
    }

    for (int i = 0; i < G.arcnum; ++i) {
        printf("请输入第%d条边的弧头、弧尾与权重：",(i+1));
        scanf("%d %d %d",&v1,&v2,&w);

        if (v1 > G.vexnum || v1 < 1 || v2 > G.vexnum || v2 < 1 )// 健全性判断
        {
            printf("输入顶点不合法！，顶点范围为%d~%d",1,G.vexnum);
            return ERROR;
        }

        v1 = LocateVex(G, v1);// 弧头顶点地址
        v2 = LocateVex(G, v2);// 弧尾顶点地址
        G.arcs[v1][v2]=G.arcs[v2][v1]=w;
    }

    return OK;
}


// 得到顶点最小值的地址
int Minimum(Closedge closedge[], int n)
{
    int i = 0, j, min, k;
    while (!closedge[i].lowcost) i++;
    min = closedge[i].lowcost;
    k = i;

    for (j = 1; j < n; j++)
        if (closedge[j].lowcost)
            if (min > closedge[j].lowcost)
            {
                min = closedge[j].lowcost;
                k = j;
            }
    return k;
}

// 构造网G的最小生成树
void MiniSpanTree_PRIM(MGraph &G, int u)
{
    Closedge closedge[G.vexnum];

    int k, j, i;
    k=j=i=0;

    k = LocateVex(G, u);//得到顶点地址G.vexs[k]
    for (j = 0; j < G.vexnum; j++)//辅助数组初始化
    {
        if (j != k)
        {
            closedge[j].adjvex = u;
            closedge[j].lowcost = G.arcs[k][j];
        }
    }

    closedge[k].lowcost = 0; //初始，U = {u}
    for (i = 1; i < G.vexnum; i++)
    { //选择其余G.vexnum-1个顶点

        k = Minimum(closedge, G.vexnum);                    //求出T的下一个结点：第k个顶点
        printf("(%d,%d)\n", closedge[k].adjvex, G.vexs[k]); //输出生成树的边

        closedge[k].lowcost = 0; //第k顶点并入U集

        for (j = 0; j < G.vexnum; ++j) // 从图7.17 第2行开始
        {
            if (G.arcs[k][j] < closedge[j].lowcost)
            { //新顶点并入U集后重新选择最小边
                closedge[j].adjvex = G.vexs[k];
                closedge[j].lowcost = G.arcs[k][j];
            }
        }
    }
}

